UVA10859 Placing Lampposts

发布于 2020-09-05 | 分类于树形dp | 3分钟 | 487字数 | 浏览量：

$n$ 个点 $m$ 条边的无向无环图，其实就是一个森林。

题目要求最小化两个量：灯数和只被一边照亮的边数。

一个做法是定义两个 $dp$ 数组，分别表示最小灯数和在灯数最小情况下的一边被照亮的最小边数。

然后你发现它们是一起转移的，那么就有一个极妙的做法：

将它们的贡献算在一起，因为灯数的优先级高，所以给它乘上一个权值 $k$ 。（这里 $k$ 可以取任意不小于 $n$ 的值，可以理解为 $k$ 进制的高低位），那么加一个灯贡献加 $k$ ，加一条单灯边贡献加 $1$ ，

那么转移就变为：

\begin{cases} dp[u][0]=\sum_{v \in son_u} dp[v][1]+1 \\ dp[u][1]=k+\sum_{v \in son_u} \min\{ dp[v][0]+1,dp[v][1] \} \end{cases}

最后只需要除以 $k$ ，和膜 $k$ 便能得到分别的答案。

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 1000 , k = 1005;
int T , n , m;
vector< int > Graph[ MAXN + 5 ];

int dp[ 2 ][ MAXN + 5 ];
void dfs( int u , int fa ) {
    dp[ 0 ][ u ] = 0 , dp[ 1 ][ u ] = k;
    for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( v == fa ) continue;
        dfs( v , u );
        dp[ 0 ][ u ] += dp[ 1 ][ v ] + 1;
        dp[ 1 ][ u ] += min( dp[ 0 ][ v ] + 1 , dp[ 1 ][ v ] );
    }
}

int main( ) {
    scanf("%d",&T);
    while( T -- ) {
        scanf("%d %d",&n,&m);
        for( int i = 1 ; i <= n ; i ++ ) Graph[ i ].clear() , dp[ 0 ][ i ] = 0 , dp[ 1 ][ i ] = 0;
        for( int i = 1 , u , v ; i <= m ; i ++ ) {
            scanf("%d %d",&u,&v); u ++ , v ++;
            Graph[ u ].push_back( v );
            Graph[ v ].push_back( u );
        }

        int Ans1 = 0 , Ans2 = 0;
        for( int i = 1 ; i <= n ; i ++ )
            if( !dp[ 1 ][ i ] ) {
                dfs( i , 0 );
                Ans1 += min( dp[ 0 ][ i ] , dp[ 1 ][ i ] ) / k;
                Ans2 += min( dp[ 0 ][ i ] , dp[ 1 ][ i ] ) % k;
            }
        printf("%d %d %d\n", Ans1 , m - Ans2 , Ans2 );
    }
    return 0;
}

UVA10859 Placing Lampposts

感谢您的支持，我会继续努力的!